{ "cells": [ { "cell_type": "markdown", "metadata": { "pycharm": { "name": "#%% md\n" } }, "source": [ "# Making Chappie\n", "\n", "## Try me\n", "[![Open In Colab](../../_static/colabs_badge.png)](https://colab.research.google.com/github/ffraile/operations-research-notebooks/blob/main/docs/source/CLP/solved/Making%20Chappie%20(Solved%20linprog).ipynb)[![Binder](../../_static/binder_badge.png)](https://mybinder.org/v2/gh/ffraile/operations-research-notebooks/main?labpath=docs%2Fsource%2FCLP%2Fsolved%2FMaking%20Chappie%20(Solved%20linprog).ipynb)\n", "\n", "## Problem definition\n", "The company Tetravaal located in Johannesburg manufactures two types of robots, Model $P_{1}$ and Model $P_{2}$. The production plant is consisted of four different sections: metal machining, plastic moulding, electrical work and assembly. \n", "The metal machining section has a capacity of 7500 units of $P_{1}$ or 6000 units of $P_{2}$ per month. \n", "\n", "Plastic moulding can process 5000 units of $P_{1}$ or 9000 units of $P_{2}$ per month.\n", "\n", "Electrical work can process 6000 units of $P_{1}$ or 7000 units of $P_{2}$ per month.\n", "\n", "In Assembly, there are two assembly lines that work in parallel, one per each robot model.\n", "\n", "The first assembly line can process 4000 units of $P_{1}$ per month\n", "\n", "The second assembly line can process 5000 units of $P_{2}$ per month\n", "\n", "Knowing that the unitary profit of $P_{1}$ is 500€ and that the unitary profit of $P_{2}$ is 600€, and that both robots have a great demand and therefore all manufactured robots are sold, Michelle Bradley, CEO of Tetravaal, asks his engineering team: \n", "\n", "Calculate the number of units of each robot that needs to be manufactured to maximise profit for the company." ] }, { "cell_type": "markdown", "metadata": { "pycharm": { "name": "#%% md\n" } }, "source": [ "## Model\n", "We want to maximise the company profits:\n", "\n", "$\\max z = 500x_{1} + 600x_{2}$\n", "\n", "where z represents the profits (€). The decision variables are:\n", "\n", "$x_{1}:$ units of $P_{1}$ per month\n", "$x_{2}:$ units of $P_{2}$ per month\n", "\n", "The objective function is subject to the following constraints:\n", "\n", "$x_{1}/7500+x_{2}/6000 \\leq 1$ Metal machining constraint\n", "\n", "$x_{1}/5000+x_{2}/9000 \\leq 1$ Plastic moulding constraint\n", "\n", "$x_{1}/6000 + x_{2}/7000 \\leq 1$ Electrical work constraint\n", "\n", "$x_{1} \\leq 4000$ First assembly line constraint \n", "\n", "$x_{2} \\leq 5000$ Second assembly line constraint" ] }, { "cell_type": "markdown", "metadata": { "pycharm": { "name": "#%% md\n" } }, "source": [ "## Solution using Linprog\n", "### Reformulating the problem\n", "First we need to define the problem model to the format expected by Linprog. Recall that we need to express our problem as:\n", "linear programming problems expressed in the form:\n", "\n", "$\\min z = c^T*x$\n", "\n", "s.t.\n", "$A_{ub}*x \\leq b_{ub}$\n", "\n", "\n", "$A_{uc}*x = b_{uc}$\n", "\n", "\n", "$l \\leq x \\leq u$\n", "\n", "The vector $c$ is:\n", "\n", "$$\\min z* = - z = -500*x - 600y = [-500, -660]^T*[x, y]$$\n", "\n", "$$c^T=[-500, -660]^T$$\n", "\n", "That is, since our objective function is of type *maximize*, we use the equivalent minimization problem and the solution will be the negative of our original objective variable.\n", "\n", "The matrix $A_{ub}$ is:\n", "\n", "\n", "$A_{ub} = \\begin{bmatrix}\n", "\\frac{1}{7500} & \\frac{1}{6000}\\\\\n", "\\frac{1}{5000} & \\frac{1}{9000}\\\\\n", "\\frac{1}{6000} & \\frac{1}{7000}\\\\\n", "\\end{bmatrix}$\n", "\n", "The vector $b_{ub}$ is:\n", "\n", "$b_{ub} = [1, 1, 1]^T$\n", "\n", "Now, $l$ is going to contain the minimum values of the decision variables, or **lower bound**. Since both variables need to be non-negative:\n", "\n", "$l^T = [0, 0]^T$\n", "\n", "and finally, $u$ is going to contain the maximum values or **upper bound**, since x cannot be higher than 12, the upper bounds are:\n", "\n", "\n", "$u^T = [4000, 5000]^T$" ] }, { "cell_type": "code", "execution_count": 1, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Optimization terminated successfully. (HiGHS Status 7: Optimal)\n", "result of the objective function is: 3654545.454545455\n" ] }, { "data": { "text/plain": " solution coefficients reduced costs\nx_1 2727.272727 500 0.0\nx_2 3818.181818 600 0.0", "text/html": "
\n\n\n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n
solutioncoefficientsreduced costs
x_12727.2727275000.0
x_23818.1818186000.0
\n
" }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": " RHS slacks shadow_prices\nMetal Machining 1 0.000000 3.272727e+06\nPlastic Moulding 1 0.030303 0.000000e+00\nElectrical Work 1 0.000000 3.818182e+05\nAssembly 1 1 0.318182 0.000000e+00\nAssembly 2 1 0.236364 0.000000e+00", "text/html": "
\n\n\n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n
RHSslacksshadow_prices
Metal Machining10.0000003.272727e+06
Plastic Moulding10.0303030.000000e+00
Electrical Work10.0000003.818182e+05
Assembly 110.3181820.000000e+00
Assembly 210.2363640.000000e+00
\n
" }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Let's start importing the linprog function of the optimize package of SciPy\n", "from scipy.optimize import linprog\n", "# We are going to use panda to display the results as tables using Panda\n", "import pandas as pd\n", "#And we will use numpy to perform array operations\n", "import numpy as np\n", "#We will use display and Markdown to format the output of code cells as Markdown\n", "from IPython.display import display, Markdown\n", "\n", "# Objective function coefficient vector\n", "c = np.array([-500, -600])\n", "\n", "\n", "\n", "# And the constraints, the Matrix A. Since all constraints are of type less or equal\n", "A=np.array([[1/7500, 1/6000], #Coefficients of the first constraint\n", " [1/5000, 1/9000], #Coefficients of the second constraint\n", " [1/6000, 1/7000],\n", " [1/4000, 0],\n", " [0, 1/5000]]) #Coefficients of the third constraint\n", "\n", "# And vector b\n", "b = np.array([1, 1, 1, 1, 1]) #limits of the three constraints\n", "\n", "#Bounds for x1\n", "x1_bounds = (0, None) # Here we could as well use 4000 limit, but if we do so, the shadow price would be more difficult to find within the provided solution\n", "# Bounds for x2\n", "x2_bounds = (0, None)\n", "\n", "res = linprog(c, A_ub=A, b_ub=b, bounds=[x1_bounds, x2_bounds])\n", "\n", "print(res.message)\n", "print(f\"result of the objective function is: {-res.fun}\")\n", "\n", "var_df = pd.DataFrame(index=['x_1', 'x_2'])\n", "var_df['solution'] = res.x\n", "var_df['coefficients'] = -c\n", "var_df['reduced costs'] = res.lower.marginals\n", "display(var_df)\n", "\n", "con_df = pd.DataFrame(index=['Metal Machining', 'Plastic Moulding', 'Electrical Work', 'Assembly 1', 'Assembly 2'])\n", "con_df['RHS'] = b\n", "con_df['slacks'] = res.slack\n", "# Since the objective function is of type maximize, we need to change the sense of the marginals\n", "con_df['shadow_prices'] = -res.ineqlin.marginals\n", "display(con_df)\n" ], "metadata": { "collapsed": false, "pycharm": { "name": "#%%\n" } } }, { "cell_type": "markdown", "source": [], "metadata": { "collapsed": false, "pycharm": { "name": "#%% md\n" } } } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.4" }, "pycharm": { "stem_cell": { "cell_type": "raw", "source": [], "metadata": { "collapsed": false } } } }, "nbformat": 4, "nbformat_minor": 2 }